/*
 * tree.c
 *
 *  Created on: Nov 28, 2010
 *      Author: cumeo89
 */

#include <glib/gmem.h>
#include <glib.h>
#include "node.h"
#include "edge.h"
#include "suffixtree.h"
#include "util.h"

void nullCallback(SuffixTree *currentTree, gpointer userData, glong i, glong j) {
	// DO NOTHING
}

#define addLeaf(v, index, i, newLeaves) {\
	Edge *_newLeafEdge = e_new(index, i, -1);\
	n_addEdge(v, _newLeafEdge);\
	newLeaves = g_slist_prepend(newLeaves, _newLeafEdge->child);\
}

void addString(SuffixTree *tree, Ucs4String **stringArr, int index,
		TreeConstructionCallback callback, gpointer userData) {
	gunichar *s = stringArr[index]->s;
	glong m = stringArr[index]->m;

	int j = 1, i = 0;
	Node *v = tree->root, *prevInner = NULL;
	GSList *newLeaves = NULL;

	// match as much prefix as possible
	for ( ; i < m; ) {
		Edge *e = n_getEdge(v, s[i], stringArr);
		if (e == NULL) {
			addLeaf(v, index, i, newLeaves);
			callback(tree, userData, i, j);
			break;
		} else {
			glong gamma = e->start;
			for (; gamma <= e->end; gamma++) {
				if (stringArr[e->stringIndex]->s[gamma] == s[i]) {
					i++;
				} else {
					break;
				}
			}
			if (gamma <= e->end) {
				e = e_split(e, gamma-e->start);
				prevInner = v = e->child;
				addLeaf(v, index, i, newLeaves);
				callback(tree, userData, i, j);
				break;
			} else {
				v = e->child;
			}
		}
	}

	// extend tree
	for ( ; i < m; i++) {
		gboolean rule3Applied = FALSE;
		Node *p = v;

		for ( ; j < i && !rule3Applied; j++) {
			p = v;

			// move v to correct position
			glong g = 0;
			if (v->link == NULL) {
				// v is a leaf or internal node without suffix link (never be the root)

				glong gamma;
				gunichar *gammaStr;

				Edge *e = n_getParentEdge(v);
				v = n_getParent(v);
				gammaStr = stringArr[e->stringIndex]->s;
				if (v == tree->root) {
					gamma = e->start + 1;
					g = e_length(e, i) - 1;
				} else {
					gamma = e->start;
					g = e_length(e, i);
					v = v->link;
				}

				gboolean done = (g == 0);
				while (!done) {
					Edge *e = n_getEdge(v, gammaStr[gamma], stringArr);
					v = e->child;
					glong l = e_length(e, i);
					if (g <= l) {
						done = TRUE;
					}
					if (g >= l) {
						gamma += l;
						g -= l;
					}
				}
			} else {
				v = v->link;
			}

			// apply one of three rules
			if (g == 0) { // the path ends at a node
				if (n_isLeaf(v)) { // rule 1
					// DO NOTHING
				} else {
					if (prevInner != NULL) {
						prevInner->link = v;
						prevInner = NULL;
					}

					Edge *e = n_getEdge(v, s[i], stringArr);
					if (e == NULL) { // rule 2
						addLeaf(v, index, i, newLeaves);
						callback(tree, userData, i, j);
					} else { // rule 3
						rule3Applied = TRUE;
					}
				}
			} else { // the path ends in the middle of an edge
				Edge *e = n_getParentEdge(v);
				if (e_charAt(e, g, stringArr) == s[i]) { // rule 3
					rule3Applied = TRUE;
				} else { // rule 2
					e = e_split(e, g);
					v = e->child;
					addLeaf(v, index, i, newLeaves);

					if (prevInner != NULL) {
						prevInner->link = v;
					}
					prevInner = v;

					callback(tree, userData, i, j);
				}
			}
		}

		// append the last single character
		if (n_getEdge(tree->root, s[i], stringArr) == NULL) {
			addLeaf(tree->root, index, i, newLeaves);
		}
		if (prevInner != NULL) {
			prevInner->link = tree->root;
			prevInner = NULL;
		}
		callback(tree, userData, i, j);

		// restore previous position, move to S[j..i] if needed
		j--;
		v = p;
		Edge *e = n_getEdge(v, s[i], stringArr);
		if (e != NULL) {
			v = e->child;
		}
	} // end for i

	g_slist_foreach(iter, newLeaves) {
		Node *leaf = iter->data;
		leaf->parentEdge->end = m-1;
	}
	g_slist_free(newLeaves);
}

void constructTree(SuffixTree *tree, const gchar **utf8Strings, TreeConstructionCallback callback, gpointer userData) {
	tree->root = n_new();

	Ucs4String **stringArr = utf8ToUcs4All(utf8Strings);
	int i;
	for (i = 0; stringArr[i] != NULL; i++) {
		addString(tree, stringArr, i, callback, userData);
	}
}

SuffixTree *t_new(const gchar **utf8String) {
	return t_new_callback(utf8String, nullCallback, NULL);
}

SuffixTree *t_new_callback(const gchar **utf8String, TreeConstructionCallback callback, gpointer userData) {
	SuffixTree *tree = g_new(SuffixTree, 1);
	tree->strings = utf8String;
	constructTree(tree, utf8String, callback, userData);
	return tree;
}

void t_free(SuffixTree *tree) {
	n_free(tree->root);
	g_free(tree);
}
